In the related art, there is an established technology that searches for a character string by comparing a pattern character string against a target character string in 1-byte units. According to this technology, when searching for a pattern character string “queen” against a target character string “The quick brown fox”, for example, after comparing the 5th byte “q” and the 6th byte “u” of the target character string, it is determined that the search result is different by a comparison of the 7th byte “i” of the target character string and “e” of the pattern character string.
In addition, there is an established technology that checks a pattern character string against a target character string by using a state transition diagram. A state transition diagram is a diagram that represents how states transition. By conducting a search using a state transition diagram, in the above example, after comparison of the 7th byte “i” of the target character string and “e” of the pattern character string finishes, the next search start position is controlled to become the 8th byte of the target character string, for example.
Also, there is an established technology that uses multiple registers to execute part of the search process that searches for a character string with hardware processing. Specifically, a device of the related art holds long-data-length data from the checking or checked character string in a first register, and shiftably holds short data in a second register. Also, a device of the related art temporarily holds in a third register data of the first character of the character string held in the second register, such that the size of the data is equal to the size of the character string held in the first register, and holds the computational result of the exclusive OR of the character string data held in the first register and the third register. In addition, the device of the related art shifts the character string in the second register by this computational result, and judges whether or not to output a search result or whether or not to shift further according to the computational result of the exclusive OR of the data held in the first register and the second register, and the shift position of the character string in the second register.
However, according to the technology of the related art, there is a problem in that if the target character string or pattern character string becomes longer, the processing time taken by a character string search greatly increases. For example, when a disparity is found between the target character string and the pattern character string, the search process is conducted again starting from the character string one byte later in the target character string, which leads to great increases in the processing time taken by a character string search. Also, in the case of creating a state transition diagram every time a search is conducted, the processing load for creating a state transition diagram increases greatly. Also, in the case of processing the pattern character string itself, another shift process is conducted when searching for the same character string again, leading to great increases in the processing time taken by a character string search.
Japanese Laid-open Patent Publication No. 2002-312364 is known as the related art, for example.